{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Points with Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扣分后的最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的整数矩阵 <code>points</code> （下标从 <strong>0</strong> 开始）。一开始你的得分为 <code>0</code> ，你想最大化从矩阵中得到的分数。</p>\n",
    "\n",
    "<p>你的得分方式为：<strong>每一行</strong> 中选取一个格子，选中坐标为 <code>(r, c)</code> 的格子会给你的总得分 <strong>增加</strong> <code>points[r][c]</code> 。</p>\n",
    "\n",
    "<p>然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 <code>r</code> 和 <code>r + 1</code> （其中 <code>0 <= r < m - 1</code>），选中坐标为 <code>(r, c<sub>1</sub>)</code> 和 <code>(r + 1, c<sub>2</sub>)</code> 的格子，你的总得分 <b>减少</b> <code>abs(c<sub>1</sub> - c<sub>2</sub>)</code> 。</p>\n",
    "\n",
    "<p>请你返回你能得到的 <strong>最大</strong> 得分。</p>\n",
    "\n",
    "<p><code>abs(x)</code> 定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>x >= 0</code> ，那么值为 <code>x</code> 。</li>\n",
    "\t<li>如果 <code>x < 0</code> ，那么值为 <code>-x</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-40-26-diagram-drawio-diagrams-net.png\" style=\"width: 300px; height: 300px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>points = [[1,2,3],[1,5,1],[3,1,1]]\n",
    "<b>输出：</b>9\n",
    "<strong>解释：</strong>\n",
    "蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。\n",
    "你的总得分增加 3 + 5 + 3 = 11 。\n",
    "但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。\n",
    "你的最终得分为 11 - 2 = 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-42-14-diagram-drawio-diagrams-net.png\" style=\"width: 200px; height: 299px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>points = [[1,5],[2,3],[4,2]]\n",
    "<b>输出：</b>11\n",
    "<strong>解释：</strong>\n",
    "蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。\n",
    "你的总得分增加 5 + 3 + 4 = 12 。\n",
    "但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。\n",
    "你的最终得分为 12 - 1 = 11 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == points.length</code></li>\n",
    "\t<li><code>n == points[r].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= m * n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= points[r][c] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-points-with-cost](https://leetcode.cn/problems/maximum-number-of-points-with-cost/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-points-with-cost](https://leetcode.cn/problems/maximum-number-of-points-with-cost/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[1,5,1],[3,1,1]]', '[[1,5],[2,3],[4,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [0]*len(queries)\n",
    "        idx = sorted(range(len(queries)), key=lambda i: queries[i])\n",
    "        _min = grid[0][0]\n",
    "        level = [(_min, 0, 0)]\n",
    "        grid[0][0] = -1\n",
    "        last = 0\n",
    "        q = deque()\n",
    "        for i in idx:\n",
    "            qv = queries[i]\n",
    "            if _min >= qv:\n",
    "                res[i] = last\n",
    "                continue\n",
    "            top = -1\n",
    "            _min = float('inf')\n",
    "            for pos, t in enumerate(level):\n",
    "                v, r, c = t\n",
    "                if v < qv:\n",
    "                    q.append((r, c))\n",
    "                    if top < 0:\n",
    "                        top = pos\n",
    "                else:\n",
    "                    _min = min(_min, v)\n",
    "                    if top >= 0:\n",
    "                        level[top] = t\n",
    "                        top += 1\n",
    "            if q:\n",
    "                del level[top:]\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                last += 1\n",
    "                for nr, nc in [(r-1, c), (r+1,c), (r, c-1), (r, c+1)]:\n",
    "                    if 0 <= nr < m and 0 <= nc < n:\n",
    "                        v = grid[nr][nc]\n",
    "                        if v < 0: continue\n",
    "                        grid[nr][nc] = -1\n",
    "                        if v < qv:\n",
    "                            q.append((nr, nc))\n",
    "                        else:\n",
    "                            level.append((v, nr, nc))\n",
    "                            _min = min(_min, v)\n",
    "            res[i] = last\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0 \n",
    "        cnt = 0\n",
    "\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0 \n",
    "            ans[qi] = cnt\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 1. 离线查询 + 并查集\n",
    "        # 矩阵元素值从小到达排序，询问也从小到大排序，双指针遍历矩阵元素值和询问，并查集实现相连的过程，同时维护每个连通块的大小\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # mn = m * n\n",
    "\n",
    "        # fa = list(range(mn))\n",
    "        # size = [1] * mn\n",
    "        # def find(x: int) -> int:\n",
    "        #     if fa[x] != x:\n",
    "        #         fa[x] = find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # def merge(from_: int, to: int) -> None:\n",
    "        #     from_ = find(from_)\n",
    "        #     to = find(to)\n",
    "        #     if from_ != to:\n",
    "        #         fa[from_] = to\n",
    "        #         size[to] += size[from_]\n",
    "\n",
    "        \n",
    "        # # 矩阵元素从小到大排序，方便离线\n",
    "        # a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        # ans, j = [0] * len(queries), 0\n",
    "        # # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        # for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "        #     while j < mn and a[j][0] < q:\n",
    "        #         _, x, y = a[j]\n",
    "        #         # 枚举周围四个格子，值小于 q 才可以合并\n",
    "        #         for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "        #             if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "        #                 merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "        #         j += 1\n",
    "        #     if grid[0][0] < q:\n",
    "        #         ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        # return ans\n",
    "                \n",
    "        # 2. 离线查询 + 最小堆\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        q = [[grid[0][0], 0, 0]]\n",
    "        grid[0][0] = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        qn = len(queries)\n",
    "        idx = list(range(qn))\n",
    "        idx.sort(key=lambda i: queries[i])\n",
    "        dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "        cnt = 0\n",
    "        ret = [0] * qn\n",
    "        for i in idx:\n",
    "            k = queries[i]\n",
    "            while q and q[0][0] < k:\n",
    "                point, x, y = heappop(q)\n",
    "                cnt += 1\n",
    "                for dx, dy in dirs:\n",
    "                    x2, y2 = x + dx, y + dy\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2]:\n",
    "                        heappush(q, [grid[x2][y2], x2, y2])\n",
    "                        grid[x2][y2] = 0\n",
    "            ret[i] = cnt\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0\n",
    "        cnt = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0\n",
    "            ans[qi] = cnt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0\n",
    "        cnt = 0\n",
    "        for qi, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                val, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                            heappush(h, (grid[x][y], x, y))\n",
    "                            grid[x][y] = 0\n",
    "            ans[qi] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        h = [(grid[0][0], 0, 0)]\n",
    "        grid[0][0] = 0  # 充当 vis 数组的作用\n",
    "        cnt = 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while h and h[0][0] < q:\n",
    "                cnt += 1\n",
    "                _, i, j = heappop(h)\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        heappush(h, (grid[x][y], x, y))\n",
    "                        grid[x][y] = 0  # 充当 vis 数组的作用\n",
    "            ans[qi] = cnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        q = [(x, i) for i, x in enumerate(queries)]\n",
    "        q.sort()\n",
    "        sl = SortedList([(grid[0][0], (0, 0))])\n",
    "        grid[0][0] = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [0] * len(q)\n",
    "        cnt = 0\n",
    "        # print(q)\n",
    "        for a, k in q: \n",
    "            while sl and sl[0][0] < a:\n",
    "                cnt += 1\n",
    "                i, j = sl[0][1]\n",
    "                sl.remove(sl[0])\n",
    "                for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                        sl.add((grid[x][y], (x, y)))\n",
    "                        grid[x][y] = 0\n",
    "                # print(sl, sl[0][0], a)\n",
    "                # print(sl and sl[0][0] < x)\n",
    "            ans[k] = cnt\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def next_pos(i, j):\n",
    "            if i > 0:\n",
    "                yield i - 1, j\n",
    "            \n",
    "            if j > 0:\n",
    "                yield i, j - 1\n",
    "\n",
    "            if i < m - 1:\n",
    "                yield i + 1, j\n",
    "            \n",
    "            if j < n - 1:\n",
    "                yield i, j + 1\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[0][0] = grid[0][0]\n",
    "\n",
    "        while q:\n",
    "            x, i, j = heappop(q)\n",
    "\n",
    "            if dist[i][j] < x:\n",
    "                continue\n",
    "            # print(x, i, j, grid[i][j], d)\n",
    "\n",
    "            for a, b in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                if 0 <= a < m and 0 <= b < n:\n",
    "                    xnew = max(x, grid[a][b])\n",
    "\n",
    "                    if xnew < dist[a][b]:\n",
    "                        dist[a][b] = xnew\n",
    "                        heappush(q, (xnew, a, b))\n",
    "\n",
    "        cnt = Counter(dist[i][j] for i in range(m) for j in range(n))\n",
    "\n",
    "        pres_k = list(sorted(cnt.keys()))\n",
    "        pres_v = list(accumulate(cnt[k] for k in pres_k))\n",
    "\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        for i, k in enumerate(queries):\n",
    "            if k > pres_k[0]:\n",
    "                ret[i] = pres_v[bisect.bisect_left(pres_k, k) - 1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def next_pos(i, j):\n",
    "            if i > 0:\n",
    "                yield i - 1, j\n",
    "            \n",
    "            if j > 0:\n",
    "                yield i, j - 1\n",
    "\n",
    "            if i < m - 1:\n",
    "                yield i + 1, j\n",
    "            \n",
    "            if j < n - 1:\n",
    "                yield i, j + 1\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[0][0] = grid[0][0]\n",
    "\n",
    "        while q:\n",
    "            x, i, j = heappop(q)\n",
    "\n",
    "            if dist[i][j] < x:\n",
    "                continue\n",
    "\n",
    "            for a, b in next_pos(i, j):\n",
    "                xnew = max(x, grid[a][b])\n",
    "\n",
    "                if xnew < dist[a][b]:\n",
    "                    dist[a][b] = xnew\n",
    "                    heappush(q, (xnew, a, b))\n",
    "\n",
    "        cnt = Counter(dist[i][j] for i in range(m) for j in range(n))\n",
    "\n",
    "        pres_k = list(sorted(cnt.keys()))\n",
    "        pres_v = list(accumulate(cnt[k] for k in pres_k))\n",
    "\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        for i, k in enumerate(queries):\n",
    "            if k > pres_k[0]:\n",
    "                ret[i] = pres_v[bisect.bisect_left(pres_k, k) - 1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        qn = len(queries)\n",
    "        sortedIndex = list(range(qn))\n",
    "        sortedIndex.sort(key=lambda x: queries[x])\n",
    "        ans = [0 for _ in range(qn)]\n",
    "        wl = [(grid[0][0], (0,0))]\n",
    "        cl = collections.deque()\n",
    "        added = [[False for _ in range(n)] for _ in range(m)]\n",
    "        added[0][0] = True\n",
    "        curPoint = 0\n",
    "        for i in range(qn):\n",
    "            qi = sortedIndex[i]\n",
    "            cap = queries[qi]\n",
    "            finished = False\n",
    "            while wl and not finished:\n",
    "                minVal, minIndex = wl[0]\n",
    "                if minVal < cap:\n",
    "                    cl.append(minIndex)\n",
    "                    heapq.heappop(wl)\n",
    "                else:\n",
    "                    finished = True\n",
    "            while cl:\n",
    "                curloc = cl.popleft()\n",
    "                curPoint+=1\n",
    "                for dx, dy in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n",
    "                    nx, ny = curloc[0]+dx, curloc[1]+dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not added[nx][ny]:\n",
    "                        added[nx][ny] = True\n",
    "                        if grid[nx][ny] < cap:\n",
    "                            cl.append((nx, ny))\n",
    "                        else:\n",
    "                            heapq.heappush(wl, (grid[nx][ny], (nx, ny)))\n",
    "            print(i, curPoint)\n",
    "            ans[qi] = curPoint\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        k = len(queries)\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        z = []\n",
    "        for i,x in enumerate(queries):\n",
    "            z.append((x,i))\n",
    "        z.sort()\n",
    "        ans = [0] * k\n",
    "        q = PriorityQueue()\n",
    "        q.put((grid[0][0],0,0))\n",
    "        cnt = 0\n",
    "        vis[0][0] = True\n",
    "        for i in range(k):\n",
    "            mx = z[i][0]\n",
    "            while not q.empty() and q.queue[0][0] < mx:           \n",
    "                _,x,y = q.get()\n",
    "                cnt += 1\n",
    "                for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = True\n",
    "                        q.put((grid[nx][ny],nx,ny))\n",
    "            ans[z[i][1]] = cnt\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.maxPoints([[1,2,3],[2,5,7],[3,5,1]],[5,6,2])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        k = len(queries)\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        z = []\n",
    "        for i,x in enumerate(queries):\n",
    "            z.append((x,i))\n",
    "        z.sort()\n",
    "        ans = [0] * k\n",
    "        q = PriorityQueue()\n",
    "        q.put((grid[0][0],0,0))\n",
    "        cnt = 0\n",
    "        vis[0][0] = True\n",
    "        for i in range(k):\n",
    "            mx = z[i][0]\n",
    "            while not q.empty():           \n",
    "                c,x,y = q.get()\n",
    "                if c < mx:\n",
    "                    cnt += 1\n",
    "                    for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                        if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                            vis[nx][ny] = True\n",
    "                            q.put((grid[nx][ny],nx,ny))\n",
    "                else:\n",
    "                    q.put((c,x,y))\n",
    "                    break\n",
    "            ans[z[i][1]] = cnt\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.maxPoints([[1,2,3],[2,5,7],[3,5,1]],[5,6,2])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        res, queries, already, heap, score, towards = [0 for _ in range(len(queries))], sorted([queries[i], i] for i in range(len(queries))), [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))], [[grid[0][0], [0, 0]]], 0, [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        already[0][0] = 1\n",
    "        for i in range(len(queries)):\n",
    "            while heap and heap[0][0] < queries[i][0]:\n",
    "                pres = heappop(heap)[1]\n",
    "                score += 1\n",
    "                for x in towards:\n",
    "                    if 0 <= pres[0] + x[0] < len(grid) and 0 <= pres[1] + x[1] < len(grid[0]) and not already[pres[0] + x[0]][pres[1] + x[1]]:\n",
    "                        already[pres[0] + x[0]][pres[1] + x[1]] = 1\n",
    "                        heappush(heap, [grid[pres[0] + x[0]][pres[1] + x[1]], [pres[0] + x[0], pres[1] + x[1]]])\n",
    "            res[queries[i][1]] = score\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        a = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a.append((grid[i][j], i, j))\n",
    "        a.sort()\n",
    "        q = sorted(enumerate(queries), key=lambda x:x[1])\n",
    "        ans = [0] * len(q)\n",
    "        dsu = Dsu(m * n)\n",
    "        j = 0\n",
    "        # print(f'{a}')\n",
    "        for i, x in q:\n",
    "            while j < len(a) and a[j][0] < x:\n",
    "                _, r, c = a[j]\n",
    "                for nr, nc in (r + 1, c),(r - 1, c),(r, c + 1), (r, c - 1):\n",
    "                    if not (0 <= nr < m and 0 <= nc < n): continue\n",
    "                    if grid[nr][nc] < x:\n",
    "                        dsu.merge(r * n + c, nr * n + nc)\n",
    "                j += 1\n",
    "            if grid[0][0] < x:\n",
    "                p = dsu.find(0)\n",
    "                ans[i] = dsu.rk[p] \n",
    "        return ans\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "        self.rk = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            self.pa[x] = y\n",
    "            self.rk[y] += self.rk[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        heap = [[grid[0][0], 0]]\n",
    "        visit = set([0])\n",
    "        qr = sorted([(idx, q) for idx, q in enumerate(queries)], key = lambda x: x[1])\n",
    "        res = [0] * len(queries)\n",
    "        cnt = 0\n",
    "        for idx, limit in qr:\n",
    "            while heap and heap[0][0] < limit:\n",
    "                _, coor = heapq.heappop(heap)\n",
    "                cnt += 1 \n",
    "                i, j = coor // n, coor % n \n",
    "                for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < m and 0 <= y < n and x * n + y not in visit:\n",
    "                        visit.add(x * n + y)\n",
    "                        heapq.heappush(heap, [grid[x][y], x * n + y])\n",
    "            res[idx] = cnt \n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [0] * len(queries)\n",
    "        qr = sorted([(idx, q) for idx, q in enumerate(queries)], key = lambda x: x[1])\n",
    "        heap = [[grid[0][0], 0]]\n",
    "        visit = set([0])\n",
    "        cnt = 0\n",
    "        for idx, limit in qr:\n",
    "            while heap and heap[0][0] < limit:\n",
    "                cnt += 1 \n",
    "                _, coor = heapq.heappop(heap)\n",
    "                i, j = coor // n, coor % n \n",
    "                for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                    x = i + d[0]\n",
    "                    y = j + d[1]\n",
    "                    if 0 <= x < m and 0 <= y < n and x * n + y not in visit:\n",
    "                        visit.add(x * n + y)\n",
    "                        heapq.heappush(heap, [grid[x][y], x * n + y])\n",
    "            res[idx] = cnt \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, a):\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        if self.find(b) != self.find(a):\n",
    "            self.size[self.find(a)] += self.size[self.find(b)]\n",
    "            self.parent[self.find(b)] = self.find(a)\n",
    "\n",
    "    def getSize(self, a):\n",
    "        return self.size[self.find(a)]\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1])\n",
    "        ans = [0] * len(queries)\n",
    "        vals = []\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                vals.append([grid[i][j], i, j])\n",
    "        vals.sort()\n",
    "        idx = 0\n",
    "        u = UnionFind(n * m)\n",
    "        for i, q in queries:\n",
    "            if grid[0][0] >= q: continue\n",
    "            while idx < len(vals) and vals[idx][0] < q:\n",
    "                x, y = vals[idx][1:]\n",
    "                for dx, dy in pairwise([0, 1, 0, -1, 0]):\n",
    "                    if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] < q:\n",
    "                        u.merge(x * m + y, (x + dx) * m + y + dy)\n",
    "                idx += 1\n",
    "            ans[i] = u.getSize(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, a):\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        if self.find(b) != self.find(a):\n",
    "            self.size[self.find(a)] += self.size[self.find(b)]\n",
    "            self.parent[self.find(b)] = self.find(a)\n",
    "\n",
    "    def getSize(self, a):\n",
    "        return self.size[self.find(a)]\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1])\n",
    "        ans = [0] * len(queries)\n",
    "        vals = []\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                vals.append([grid[i][j], i, j])\n",
    "        vals.sort()\n",
    "        idx = 0\n",
    "        u = UnionFind(n * m)\n",
    "        for i, q in queries:\n",
    "            if grid[0][0] >= q: continue\n",
    "            while idx < len(vals) and vals[idx][0] < q:\n",
    "                x, y = vals[idx][1:]\n",
    "                for dx, dy in pairwise([0, 1, 0, -1, 0]):\n",
    "                    if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] < q:\n",
    "                        u.merge(x * m + y, (x + dx) * m + y + dy)\n",
    "                idx += 1\n",
    "            ans[i] = u.getSize(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1]  * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int)->None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[to] =from_\n",
    "                size[from_] += size[to]\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "返回每次查询获得的分数 --> 连通块的大小\n",
    "离线查询+并查集\n",
    "合并的方向就定为从小到大合并\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mn=m*n\n",
    "        fa=list(range(mn))\n",
    "        sz=[1]*mn\n",
    "        def find(x:int)->int:\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        #怎么对整个矩阵排序呢？\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        #找到所有小于q[i]的单元格位置\n",
    "        ans=[0]*len(queries)\n",
    "        j=0\n",
    "        for i,q in sorted(enumerate(queries),key=lambda z:z[1]):\n",
    "            while j<mn and a[j][0]<q:\n",
    "                x,y=a[j][1],a[j][2]\n",
    "                for x2,y2 in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=x2<m and 0<=y2<n and a[j][0]>=grid[x2][y2]:\n",
    "                        #将(x2,y2)向(x,y)合并\n",
    "                        fx=find(x*n+y)\n",
    "                        fy=find(x2*n+y2)\n",
    "                        if fx==fy:\n",
    "                            continue\n",
    "                        fa[fy]=fx\n",
    "                        sz[fx]+=sz[fy]\n",
    "                j+=1\n",
    "            if grid[0][0]>=q:ans[i]=0\n",
    "            else:ans[i]=sz[find(0)]\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        a = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a.append((grid[i][j], i, j))\n",
    "        a.sort()\n",
    "        q = sorted(enumerate(queries), key=lambda x:x[1])\n",
    "        ans = [0] * len(q)\n",
    "        dsu = Dsu(m * n)\n",
    "        j = 0\n",
    "        print(f'{a}')\n",
    "        for i, x in q:\n",
    "            while j < len(a) and a[j][0] < x:\n",
    "                _, r, c = a[j]\n",
    "                for nr, nc in (r + 1, c),(r - 1, c),(r, c + 1), (r, c - 1):\n",
    "                    if not (0 <= nr < m and 0 <= nc < n): continue\n",
    "                    if grid[nr][nc] < x:\n",
    "                        dsu.merge(r * n + c, nr * n + nc)\n",
    "                j += 1\n",
    "            if grid[0][0] < x:\n",
    "                p = dsu.find(0)\n",
    "                ans[i] = dsu.rk[p] \n",
    "        return ans\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "        self.rk = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            self.pa[x] = y\n",
    "            self.rk[y] += self.rk[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        now = 0\n",
    "        ans = 0\n",
    "        heap = [(grid[0][0], 0, 0)]\n",
    "        seen = set([(0, 0)])\n",
    "        q = []\n",
    "        while heap:\n",
    "            now = heap[0][0] + 1\n",
    "            while heap and heap[0][0] < now:\n",
    "                nex, x, y = heappop(heap)\n",
    "                ans += 1\n",
    "                for a, b in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                    if 0 <= a < m and 0 <= b < n and (a, b) not in seen:\n",
    "                        seen.add((a, b))\n",
    "                        heappush(heap, (grid[a][b], a, b))\n",
    "            q.append((now, ans))\n",
    "        res = [0]*len(queries)\n",
    "        for i, k in enumerate(queries):\n",
    "            where = bisect_right(q, (k, inf))\n",
    "            if where:\n",
    "                res[i] = q[where-1][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "练习一下并查集\n",
    "离线查询，并查集合并方向->小分数向大分数合并，由于不能按秩合并，最坏情况是（在均摊计算下）NlogN\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        #并查集模板\n",
    "        #首先是对下标写并查集\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        mn=m*n\n",
    "        fa=list(range(mn))\n",
    "        size=[1]*(mn) #维护并查集内的元素个数，返回答案\n",
    "        def find(x:int)->int:\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def merge(from_:int,to:int)->None:\n",
    "            from_=find(from_)\n",
    "            to=find(to)\n",
    "            if from_!=to:\n",
    "                fa[from_]=to\n",
    "                size[to]+=size[from_]\n",
    "\n",
    "        #以后绑定下标都这么写\n",
    "        #巧妙的做法是，将矩阵元素从小到大排序，然后一边遍历，一边计算\n",
    "        a=sorted((x,i,j) for i,row in enumerate(grid) for j,x in enumerate(row))\n",
    "\n",
    "        ans,j=[0]*len(queries),0\n",
    "        for idx,q in sorted(enumerate(queries),key=lambda z:z[1]):\n",
    "            while j<mn and a[j][0]<q:\n",
    "                _,x,y=a[j]\n",
    "                for x2,y2 in (x+1,y),(x-1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=x2<m and 0<=y2<n and grid[x2][y2]<q:\n",
    "                        merge(x*n+y,x2*n+y2)\n",
    "                j+=1\n",
    "            if grid[0][0]<q:\n",
    "                ans[idx]=size[find(0)]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # mn = m * n\n",
    "\n",
    "        # fa = list(range(mn))\n",
    "        # size = [1] * mn\n",
    "\n",
    "        # def find(node):\n",
    "        #     if fa[node] != node:\n",
    "        #         fa[node] = find(fa[node])\n",
    "        #     return fa[node]\n",
    "\n",
    "        # def union(from_, to_):\n",
    "        #     x, y = find(from_), find(to_)\n",
    "\n",
    "        #     if x != y:\n",
    "        #         fa[x] = y\n",
    "        #         size[y] += size[x]\n",
    "\n",
    "        # record = []\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         record.append((grid[i][j], i, j))\n",
    "        # record.sort()\n",
    "\n",
    "        # queries_sort = [(i, q) for i, q in enumerate(queries)]\n",
    "        # queries_sort = sorted(queries_sort, key=lambda k: k[1])\n",
    "\n",
    "        # res = [0] * len(queries)\n",
    "\n",
    "        # for index, q in queries_sort:\n",
    "        #     cur = 0\n",
    "        #     while cur < mn and record[cur][0] < q:\n",
    "        #         _, x, y = record[cur]\n",
    "        #         for x_, y_ in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "        #             if 0 <= x_ < m and 0 <= y_ < n and grid[x_][y_] < q:\n",
    "        #                 union(x*n+y, x_*n+y_)\n",
    "        #         cur += 1\n",
    "\n",
    "        #     if grid[0][0] < q:\n",
    "        #         res[index] = size[find(0)]\n",
    "        # return res\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1]  * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int)->None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(from_, to):\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key=lambda x: x[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 1. 离线查询 + 并查集\n",
    "        # 矩阵元素值从小到达排序，询问也从小到大排序，双指针遍历矩阵元素值和询问，并查集实现相连的过程，同时维护每个连通块的大小\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        \n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "        a = []\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                a.append((x, i, j))\n",
    "        a.sort()\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda q: q[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集初始化\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询从小到大排序\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        mn = m * n\n",
    "\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "\n",
    "        def find(node):\n",
    "            if fa[node] != node:\n",
    "                fa[node] = find(fa[node])\n",
    "            return fa[node]\n",
    "\n",
    "        def union(from_, to_):\n",
    "            x, y = find(from_), find(to_)\n",
    "\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "                size[y] += size[x]\n",
    "\n",
    "        record = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                record.append((grid[i][j], i, j))\n",
    "        record.sort()\n",
    "\n",
    "        queries_sort = [(i, q) for i, q in enumerate(queries)]\n",
    "        queries_sort = sorted(queries_sort, key=lambda k: k[1])\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        cur = 0\n",
    "        for index, q in queries_sort:\n",
    "            while cur < mn and record[cur][0] < q:\n",
    "                _, x, y = record[cur]\n",
    "                for x_, y_ in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                    if 0 <= x_ < m and 0 <= y_ < n and grid[x_][y_] < q:\n",
    "                        union(x*n+y, x_*n+y_)\n",
    "                cur += 1\n",
    "\n",
    "            if grid[0][0] < q:\n",
    "                res[index] = size[find(0)]\n",
    "        return res\n",
    "\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_: int, to: int) -> None:\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = to\n",
    "                size[to] += size[from_]\n",
    "\n",
    "        # 矩阵元素从小到大排序，方便离线\n",
    "        a = sorted((x, i, j) for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        # 查询的下标按照查询值从小到大排序，方便离线\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                # 枚举周围四个格子，值小于 q 才可以合并\n",
    "                for x2, y2 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] < q:\n",
    "                        merge(x * n + y, x2 * n + y2)  # 把坐标压缩成一维的编号\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]  # 左上角的连通块的大小\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m * n\n",
    "        fa = list(range(mn))\n",
    "        size = [1] * mn\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(from_, to):\n",
    "            from_ = find(from_)\n",
    "            to = find(to)\n",
    "            if from_ != to:\n",
    "                fa[from_] = fa[to]\n",
    "                size[to] += size[from_]\n",
    "        a = sorted((x, i, j)for i, row in enumerate(grid) for j, x in enumerate(row))\n",
    "        ans, j = [0] * len(queries), 0\n",
    "        for i, q in sorted(enumerate(queries), key = lambda x:x[1]):\n",
    "            while j < mn and a[j][0] < q:\n",
    "                _, x, y = a[j]\n",
    "                for x1, y1 in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= x1 < m and 0 <= y1 < n and grid[x1][y1]  < q:\n",
    "                        merge(x * n + y, x1 * n + y1)\n",
    "                j += 1\n",
    "            if grid[0][0] < q:\n",
    "                ans[i] = size[find(0)]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(queries)\n",
    "        vis = {(0, 0)}\n",
    "        cnt = 0\n",
    "        q = [(grid[0][0], 0, 0)]\n",
    "        for num, idx in sorted(zip(queries, list(range(len(queries))))):\n",
    "            \n",
    "            while q and q[0][0] < num:\n",
    "                _, x, y = heapq.heappop(q)\n",
    "                cnt += 1\n",
    "                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis:\n",
    "                        vis.add((nx, ny))\n",
    "                        heapq.heappush(q, (grid[nx][ny], nx, ny))\n",
    "\n",
    "            ans[idx] = cnt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k=len(queries)\n",
    "        \n",
    "        queries=[(queries[i],i) for i in range(k)]\n",
    "        queries.sort()\n",
    "        \n",
    "        count=0\n",
    "        q=[(grid[0][0],0,0)]\n",
    "        \n",
    "        \n",
    "        ans=[0]*k\n",
    "        \n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        visited=set()\n",
    "        visited.add((0,0))\n",
    "        for e in range(k):\n",
    "            \n",
    "            while q and q[0][0]<queries[e][0]:\n",
    "                count+=1\n",
    "                _,i,j=heappop(q)\n",
    "                \n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and (newi,newj) not in visited:\n",
    "                        heappush(q,(grid[newi][newj],newi,newj))\n",
    "                        visited.add((newi,newj))\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "            ans[queries[e][1]]=count\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, grid: List[List[int]], qu: List[int]) -> List[int]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k=len(qu)\n",
    "        ans=[0]*k\n",
    "        \n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        \n",
    "        for i in range(k):\n",
    "            qu[i]=(qu[i],i)\n",
    "        qu.sort()\n",
    "        \n",
    "        count=0\n",
    "        q=[(grid[0][0],0,0)]\n",
    "        visited=set()\n",
    "        visited.add((0,0))\n",
    "        \n",
    "        for thisq,index in qu:\n",
    "            \n",
    "            while q and q[0][0]<thisq:\n",
    "                count+=1\n",
    "                _,i,j=heappop(q)\n",
    "                \n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and (newi,newj) not in visited:\n",
    "                        visited.add((newi,newj))\n",
    "                        heappush(q,(grid[newi][newj],newi,newj))\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            ans[index]=count\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m,n = len(points),len(points[0])\n",
    "        dp = [0]*n\n",
    "        max_l = [0]*n\n",
    "        dp[-1],max_l[-1] = points[0][-1],points[0][-1]-(n-1)\n",
    "        for j in range(n-2,-1,-1):\n",
    "            dp[j] = points[0][j]\n",
    "            max_l[j] = max(max_l[j+1], points[0][j]-j)\n",
    "\n",
    "        for i in range(1,m):\n",
    "            max_f = -float('inf')\n",
    "            for j in range(n):\n",
    "                max_f = max(max_f, dp[j]+j)\n",
    "                dp[j] = max(points[i][j]-j+max_f, points[i][j]+j+max_l[j])\n",
    "            max_l[-1] = dp[-1]-(n-1)\n",
    "            for j in range(n-2,-1,-1):\n",
    "                max_l[j] = max(max_l[j+1], dp[j]-j)\n",
    "            pass\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0][:]\n",
    "        for i in range(1,m):\n",
    "            dp1 = [0]*n\n",
    "            dp1[0] = dp[0] + 0\n",
    "            for j in range(1,n):\n",
    "                dp1[j] = max(dp1[j-1], dp[j]+j)\n",
    "            dp2 = [0]*n \n",
    "            dp2[n-1] = dp[n-1] - (n-1)\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp2[j] = max(dp2[j+1], dp[j]-j)\n",
    "            tmp = [0]*n\n",
    "            for j in range(n):\n",
    "                tmp[j] = max(points[i][j]-j+dp1[j], points[i][j]+j+dp2[j])\n",
    "            dp = tmp[:]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0][:]\n",
    "        for i in range(1,m):\n",
    "            dp1 = [0]*n\n",
    "            dp1[0] = dp[0]\n",
    "            for j in range(1,n):\n",
    "                dp1[j] = max(dp1[j-1], dp[j]+j)\n",
    "            dp2 = [0]*n \n",
    "            dp2[n-1] = dp[n-1]-(n-1)\n",
    "            for j in range(n-2,-1,-1):\n",
    "                dp2[j] = max(dp2[j+1], dp[j]-j)\n",
    "            tmp = [0]*n\n",
    "            for j in range(n):\n",
    "                tmp[j] = max(points[i][j]-j+dp1[j], points[i][j]+j+dp2[j])\n",
    "            dp = tmp[:]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n-1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "\n",
    "        a = [-inf] * n\n",
    "        b = [-inf] * n\n",
    "        ans = 0\n",
    "\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = points[0][i]\n",
    "            ans = max(ans, f[i])\n",
    "            a[i] = f[i] + i\n",
    "            if i > 0:\n",
    "                a[i] = max(a[i], a[i - 1])\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            b[i] = f[i] - i\n",
    "            if i + 1 < n:\n",
    "                b[i] = max(b[i], b[i + 1])\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                f[j] = max(a[j] + points[i][j] - j, b[j] + points[i][j] + j)\n",
    "                ans = max(ans, f[j])\n",
    "            for j in range(n):\n",
    "                a[j] = f[j] + j\n",
    "                if j > 0:\n",
    "                    a[j] = max(a[j], a[j - 1])\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                b[j] = f[j] - j\n",
    "                if j + 1 < n:\n",
    "                    b[j] = max(b[j], b[j + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = -inf\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            best = -inf\n",
    "            \n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            f = g\n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = points[0][::]\n",
    "        for i in range(1, m):\n",
    "            ml, mr = -inf, -inf\n",
    "            pre = dp[::]\n",
    "            for j in range(n):\n",
    "                ml = max(ml, pre[j] + j)\n",
    "                dp[j] = max(dp[j], points[i][j] - j + ml)\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mr = max(mr, pre[j] - j)\n",
    "                dp[j] = max(dp[j], points[i][j] + j + mr)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        m = len(points[0])\n",
    "        lm = [0]*m\n",
    "        rm = [0] * m\n",
    "        dp = [0]*m\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dp[j] = points[i][j] + max(lm[j],rm[j])\n",
    "            lm[0] = dp[0]\n",
    "            rm[-1] = dp[-1]\n",
    "            for j in range(1,m):\n",
    "                k = m-1-j\n",
    "                lm[j] = max(dp[j],lm[j-1]-1)\n",
    "                rm[k] = max(dp[k],rm[k+1]-1)\n",
    "            #print(dp)\n",
    "            #print(lm, rm)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        length=len(points)\n",
    "        for i in range(1,length):\n",
    "            now=points[i][:]\n",
    "            points[i][0]+=points[i-1][0]\n",
    "            last=0\n",
    "            for j in range(1,len(points[0])):\n",
    "                if points[i-1][j]>=points[i-1][last]-(j-last):\n",
    "                    points[i][j]+=points[i-1][j]\n",
    "                    last=j \n",
    "                else: points[i][j]+=points[i-1][last]-(j-last)\n",
    "            last=len(points[0])-1\n",
    "            for j in range(len(points[0])-2,-1,-1):\n",
    "                if points[i-1][j]>=points[i-1][last]-(last-j):\n",
    "                    last=j\n",
    "                else: points[i][j]=max(now[j]+points[i-1][last]-(last-j),points[i][j])\n",
    "        return max(points[-1])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0]\n",
    "        for i in range(1, m):\n",
    "            new_dp = list(dp)\n",
    "            left_max = -inf\n",
    "            right_max = -inf\n",
    "            for j in range(n):\n",
    "                left_max = max(left_max, dp[j] + j)\n",
    "                right_max = max(right_max, dp[n-1-j] - (n - 1 - j))\n",
    "                new_dp[j] = max(left_max - j + points[i][j], new_dp[j])\n",
    "                new_dp[n-1-j] = max((n - 1 - j) + right_max + points[i][n-1-j], new_dp[n-1-j])\n",
    "            dp = new_dp\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        f = [0] * n\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            if i == 0:\n",
    "                for j in range(n):\n",
    "                    f[j] = points[i][j]\n",
    "                    ans = max(ans, f[j])\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    f[j] = max(a[j] + points[i][j] - j, b[j] + points[i][j] + j)\n",
    "                    ans = max(ans, f[j])\n",
    "\n",
    "            for j in range(n):\n",
    "                a[j] = f[j] + j\n",
    "                if j > 0:\n",
    "                    a[j] = max(a[j], a[j - 1])\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                b[j] = f[j] - j\n",
    "                if j + 1 < n:\n",
    "                    b[j] = max(b[j], b[j + 1])\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0]\n",
    "        for i in range(1, m):\n",
    "            new_dp = list(dp)\n",
    "            left_max = -inf\n",
    "            right_max = -inf\n",
    "            for j in range(n):\n",
    "                left_max = max(left_max, dp[j] + j)\n",
    "                right_max = max(right_max, dp[n-1-j] - (n - 1 - j))\n",
    "                new_dp[j] = max(left_max - j + points[i][j], new_dp[j])\n",
    "                new_dp[n-1-j] = max((n - 1 - j) + right_max + points[i][n-1-j], new_dp[n-1-j])\n",
    "            dp = new_dp\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxPoints(self, points: List[List[int]]) -> int:\n",
    "#         m, n = len(points), len(points[0])\n",
    "#         dp = points[0] # 1st row points\n",
    "#         # for 2rd row 1 / 2rd col - > \n",
    "#         for i in range(1, m):\n",
    "#             # step 1: 对于所有上一行左边的数，都是加上它的坐标减去自己的坐标\n",
    "#             for j in range(1, n):\n",
    "#                 dp[j] = max(dp[j], dp[j - 1] - 1)\n",
    "#             # step 2: 对于上一行所有右边的数，都是减去它的坐标加上自己的坐标\n",
    "#             for j in range(n - 2, -1, -1):\n",
    "#                 dp[j] = max(dp[j], dp[j + 1] - 1)\n",
    "#             # 分别加上point[i][j]\n",
    "#             dp = [points[i][j] + dp[j] for j in range(n)]\n",
    "        \n",
    "#         return max(dp)\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points[0])\n",
    "        # dp[j] represents the maximum number of points we can have if points[row][j] is the most recent cell picked.\n",
    "        dp = [0] * n\n",
    "        # We will iterate through the rows and for each row, we will find the maximum sum of points considering both left-to-right and right-to-left traversal and update our dp array accordingly.\n",
    "        for row in points:\n",
    "            left_to_right = [0] * n\n",
    "            running_max = 0\n",
    "\n",
    "            # Calculate left-to-right maximums\n",
    "            for j in range(n):\n",
    "                running_max = max(running_max - 1, dp[j])\n",
    "                left_to_right[j] = running_max\n",
    "\n",
    "            right_to_left = [0] * n\n",
    "            running_max = 0\n",
    "\n",
    "            # Calculate right-to-left maximums\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                running_max = max(running_max - 1, dp[j])\n",
    "                right_to_left[j] = running_max\n",
    "\n",
    "            # Update dp array with the maximums from both left and right traversals\n",
    "            for j in range(n):\n",
    "                dp[j] = max(left_to_right[j], right_to_left[j]) + row[j]\n",
    "\n",
    "        # Return the maximum value in the dp array\n",
    "        # print(dp) # [9, 8, 7]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        \n",
    "        # 当前行的最大值初始化为points的第一行\n",
    "        curr_row_max = points[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            # 从左到右和从右到左计算前缀最大值\n",
    "            left_max = [0] * n\n",
    "            right_max = [0] * n\n",
    "            \n",
    "            left_max[0] = curr_row_max[0]\n",
    "            for j in range(1, n):\n",
    "                left_max[j] = max(left_max[j-1] - 1, curr_row_max[j])\n",
    "                \n",
    "            right_max[-1] = curr_row_max[-1]\n",
    "            for j in range(n-2, -1, -1):\n",
    "                right_max[j] = max(right_max[j+1] - 1, curr_row_max[j])\n",
    "                \n",
    "            # 更新当前行的最大值\n",
    "            for j in range(n):\n",
    "                curr_row_max[j] = points[i][j] + max(left_max[j], right_max[j])\n",
    "\n",
    "        return max(curr_row_max)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "寻找重复子问题\n",
    "f[i][j] 表示选中当前格子能够获得的最大分数\n",
    "f[i][j] = max(f[i][j], f[i-1][k] - abs(k - j))\n",
    "f[i][j] = max(f[i-1][0] - j, f[i-1][1] - j + 1, f[i-1][2]-j+2, ..., f[i-1][j], f[i-1][j+1]-1, .., f[i-1][n-1]-(n-1-j))\n",
    "f[i][j+1] = max(f[i-1][0] - j - 1, f[i-1][1] - j, f[i-1][2]-j+1, ..., f[i-1][j] - 1, f[i-1][j+1], .., f[i-1][n-1]-(n-2-j))\n",
    "f[i][j+1] = max(max(f[i-1][0] - j, f[i-1][1] - j + 1, f[i-1][2]-j+2, ..., f[i-1][j]) - 1, max(f[i-1][j+1]-1, .., f[i-1][n-1]-(n-1-j)) + 1)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxPoints(self, f: List[List[int]]) -> int:\n",
    "        m, n = len(f), len(f[0])\n",
    "        for i in range(1, m):\n",
    "            left, right = [0] * n, [0] * n\n",
    "            mx = -inf\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mx = max(mx - 1, f[i-1][j])\n",
    "                right[j] = mx\n",
    "            mx = -inf\n",
    "            for j in range(n):\n",
    "                mx = max(mx - 1, f[i-1][j])\n",
    "                left[j] = mx\n",
    "            k = 0\n",
    "            for j in range(n):\n",
    "                f[i][j] += max(left[j], right[j])\n",
    "                k += 1\n",
    "        return max(f[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float(\"-inf\")\n",
    "            # 正序遍历\n",
    "            for j in range(n):\n",
    "                best = max(best, f[j] + j)\n",
    "                g[j] = max(g[j], best + points[i][j] - j)\n",
    "            \n",
    "            best = float(\"-inf\")\n",
    "            # 倒序遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, f[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "            \n",
    "            f = g\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # f[i] = f[k] - i + k\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        f = [points[0], [0] * n]\n",
    "        left = [[0] * n, [0] * n]\n",
    "        right = [[0] * n, [0] * n]\n",
    "        def init(row, left, right, f):\n",
    "            left[0] = f[0]\n",
    "            for i in range(1, n):\n",
    "                left[i] = max(left[i - 1], f[i] + i)\n",
    "            right[n - 1] = f[n - 1] - (n - 1)\n",
    "            for i in range(n - 2, -1, -1):\n",
    "                right[i] = max(right[i + 1], f[i] - i)\n",
    "        init(points[0], left[0], right[0], f[0])\n",
    "        for i in range(1, m):\n",
    "            now = i & 1\n",
    "            pre = now ^ 1\n",
    "            f[now][0] = right[pre][0] + points[i][0]\n",
    "            for j in range(1, n - 1):\n",
    "                f[now][j] = max(left[pre][j] - j, right[pre][j + 1] + j) + points[i][j]\n",
    "            f[now][n - 1] = left[pre][n - 1] + points[i][n - 1] - (n - 1)\n",
    "            init(points[i], left[now], right[now], f[now])\n",
    "            # print(i, left[now], right[now], f[now])\n",
    "        return max(f[(m - 1) & 1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        m=len(points[0])\n",
    "        ans=max(points[0])\n",
    "        for i in range(1,n):\n",
    "            a=b=points[i-1]\n",
    "            for k in range(1,m):\n",
    "                a[k]=max(a[k-1]-1,a[k])\n",
    "            for k in range(m-2,-1,-1):\n",
    "                b[k]=max(b[k+1]-1,b[k])\n",
    "            for k in range(m):\n",
    "                points[i][k]=points[i][k]+max(a[k],b[k])\n",
    "                ans=max(ans,points[i][k])\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "\n",
    "        a = [0] * n\n",
    "        b = [0] * n\n",
    "        f = [0] * n\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            if i == 0:\n",
    "                for j in range(n):\n",
    "                    f[j] = points[i][j]\n",
    "                    ans = max(ans, f[j])\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    f[j] = max(a[j] + points[i][j] - j, b[j] + points[i][j] + j)\n",
    "                    ans = max(ans, f[j])\n",
    "\n",
    "            for j in range(n):\n",
    "                a[j] = f[j] + j\n",
    "                b[n - 1 - j] = f[n - 1 - j] - (n - 1 - j)\n",
    "                if j > 0:\n",
    "                    a[j] = max(a[j], a[j - 1])\n",
    "                    b[n - 1 - j] = max(b[n - 1 - j], b[n - j])\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        pre = points[0][:]\n",
    "        for i in range(1, m):\n",
    "            cur = [-inf] * n\n",
    "            left = -inf\n",
    "            for j in range(n):\n",
    "                left = left if left > pre[j] + j else pre[j] + j\n",
    "                cur[j] = max(cur[j], left - j + points[i][j])\n",
    "\n",
    "            left = -inf\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                left = left if left > pre[j] - j else pre[j] - j\n",
    "                cur[j] = max(cur[j], left + j + points[i][j])\n",
    "            pre = cur[:]\n",
    "\n",
    "        return max(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        if n == 1:\n",
    "            return sum(point[0] for point in points)\n",
    "        if m == 1:\n",
    "            return max(points[0])\n",
    "        dp = [0] * n\n",
    "        for i in range(m):\n",
    "            g = [0] * n\n",
    "            best = float('-inf')\n",
    "            for j in range(n):\n",
    "               best = max(best, dp[j] + j)\n",
    "               g[j] = max(g[j], best + points[i][j] - j)\n",
    "\n",
    "            best = float('-inf')\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                best = max(best, dp[j] - j)\n",
    "                g[j] = max(g[j], best + points[i][j] + j)\n",
    "\n",
    "            dp = g \n",
    "\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def maxPoints(self, points: List[List[int]]) -> int:\n",
    "    m, n = len(points), len(points[0])\n",
    "    f = points[0].copy()\n",
    "    for i in range(1, m):\n",
    "      maxl = maxr = float(\"-inf\")\n",
    "      cp = f.copy()\n",
    "      for j in range(n):\n",
    "        maxl = max(maxl, cp[j]+j)\n",
    "        f[j] = max(f[j], points[i][j]-j+maxl)\n",
    "      for j in range(n-1, -1, -1):\n",
    "        maxr = max(maxr, cp[j]-j)\n",
    "        f[j] = max(f[j], points[i][j]+j+maxr)\n",
    "    return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n, m = len(points[0]), len(points)\n",
    "        r_max = [0] * n\n",
    "        for r in range(m):\n",
    "            now_r = [0] * n\n",
    "            left_max = float(\"-inf\")\n",
    "            for c in range(n):\n",
    "                left_max = max(left_max, r_max[c] + c)\n",
    "                now_r[c] = max(now_r[c], left_max + points[r][c] - c)\n",
    "            \n",
    "            right_max = float(\"-inf\")\n",
    "            for c in range(n - 1, -1, -1):\n",
    "                right_max = max(right_max, r_max[c] - c)\n",
    "                now_r[c] = max(now_r[c], right_max + points[r][c] + c)\n",
    "\n",
    "            r_max = now_r\n",
    "            \n",
    "        return max(r_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points[0])\n",
    "        f = points[0][:]\n",
    "        for p in points[1:]:\n",
    "            g = [0] * n\n",
    "            lmx = -inf\n",
    "            for j in range(n):\n",
    "                lmx = max(lmx, f[j] + j)\n",
    "                g[j] = max(g[j], p[j] + lmx - j)\n",
    "            rmx = -inf\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                rmx = max(rmx, f[j] - j)\n",
    "                g[j] = max(g[j], p[j] + rmx + j)\n",
    "            f = g\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [i for i in points[0]]\n",
    "        for i in range(1, m):\n",
    "            suf = [-inf] * (n + 1)\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                suf[j] = max(suf[j + 1], f[j] - j)\n",
    "            p = 0\n",
    "            g = [-inf] * n\n",
    "            for j in range(n):\n",
    "                p = max(p, f[j] + j)\n",
    "                g[j] = max(suf[j + 1] + j, p - j) + points[i][j]\n",
    "            f = g\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = [i for i in points[0]]\n",
    "        for i in range(1, m):\n",
    "            suf = [-inf] * (n + 1)\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                suf[j] = max(suf[j + 1], f[j] - j)\n",
    "            p = -inf\n",
    "            g = [0] * n\n",
    "            for j in range(n):\n",
    "                p = max(p, f[j] + j)\n",
    "                g[j] = max(suf[j + 1] + j, p - j) + points[i][j]\n",
    "            f = g\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp_pre = [points[0][j] for j in range(n)]\n",
    "        dp_cur = [points[0][j] for j in range(n)]\n",
    "        for i in range(1,m):\n",
    "            cur_max = -float('inf')\n",
    "            for j in range(n):\n",
    "                cur_max = max(cur_max, dp_pre[j]+j)\n",
    "                dp_cur[j] = cur_max + points[i][j]-j\n",
    "            cur_max = -float('inf')\n",
    "            for j in range(n-1, -1, -1):\n",
    "                cur_max = max(cur_max, dp_pre[j]-j)\n",
    "                dp_cur[j] = max(dp_cur[j], cur_max + points[i][j]+j)\n",
    "            dp_pre = dp_cur.copy()\n",
    "        return max(dp_cur[j] for j in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        for i in range(1, len(points)):\n",
    "            left,right = self.addfromleft(points[i-1]), self.addfromright(points[i-1])\n",
    "            for j in range(len(points[0])):\n",
    "                points[i][j] = max(left[j], right[j]) + points[i][j]\n",
    "        return max(points[-1][:])\n",
    "        \n",
    "    def addfromleft(self, arr):\n",
    "        resleft = [arr[0]] + [0 for _ in range(len(arr)-1)]\n",
    "        for i in range(1, len(resleft)):\n",
    "            resleft[i] = max(resleft[i-1]-1, arr[i])\n",
    "        return resleft\n",
    "    \n",
    "    def addfromright(self, arr):\n",
    "        resright = [0 for _ in range(len(arr)-1)] + [arr[-1]]\n",
    "        for i in range(len(arr)-2, -1, -1):\n",
    "            resright[i] = max(resright[i+1]-1, arr[i])\n",
    "        return resright\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = points[0] # 1st row points [1, 2, 3]\n",
    "        # for 2rd row 1 / 2rd col - > \n",
    "        for i in range(1, m):\n",
    "            # step 1: 对于所有上一行左边的数，都是加上它的坐标减去自己的坐标\n",
    "            for j in range(1, n):\n",
    "                dp[j] = max(dp[j], dp[j - 1] - 1)\n",
    "            # print(\"*\", dp) [1, 2, 3] -> [2, 7, 6]\n",
    "            # step 2: 对于上一行所有右边的数，都是减去它的坐标加上自己的坐标\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[j] = max(dp[j], dp[j + 1] - 1)\n",
    "            # print(dp) [1, 2, 3]-> [6, 7, 6]\n",
    "            # 分别加上point[i][j]\n",
    "            dp = [points[i][j] + dp[j] for j in range(n)]\n",
    "        \n",
    "        return max(dp)\n",
    "# class Solution:\n",
    "#     def maxPoints(self, points: List[List[int]]) -> int:\n",
    "#         n = len(points[0])\n",
    "#         # dp[j] represents the maximum number of points we can have if points[row][j] is the most recent cell picked.\n",
    "#         dp = [0] * n\n",
    "#         # We will iterate through the rows and for each row, we will find the maximum sum of points considering both left-to-right and right-to-left traversal and update our dp array accordingly.\n",
    "#         for row in points:\n",
    "#             left_to_right = [0] * n\n",
    "#             running_max = 0\n",
    "\n",
    "#             # Calculate left-to-right maximums\n",
    "#             for j in range(n):\n",
    "#                 running_max = max(running_max - 1, dp[j])\n",
    "#                 left_to_right[j] = running_max\n",
    "\n",
    "#             right_to_left = [0] * n\n",
    "#             running_max = 0\n",
    "\n",
    "#             # Calculate right-to-left maximums\n",
    "#             for j in range(n - 1, -1, -1):\n",
    "#                 running_max = max(running_max - 1, dp[j])\n",
    "#                 right_to_left[j] = running_max\n",
    "\n",
    "#             # Update dp array with the maximums from both left and right traversals\n",
    "#             for j in range(n):\n",
    "#                 dp[j] = max(left_to_right[j], right_to_left[j]) + row[j]\n",
    "\n",
    "#         # Return the maximum value in the dp array\n",
    "#         # print(dp) # [9, 8, 7]\n",
    "#         return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = points[0] # 1st row points [1, 2, 3]\n",
    "        # for 2rd row 1 / 2rd col - > \n",
    "        for i in range(1, m):\n",
    "            # step 1a: [从左上方来 last_total points -cost]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = max(dp[j], dp[j - 1] - 1)\n",
    "            # print(\"*\", dp) [1, 2, 3] -> [2, 7, 6]\n",
    "            # step 1b: [从右上方来last total points -cost]\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[j] = max(dp[j], dp[j + 1] - 1)\n",
    "            # print(dp) [1, 2, 3]-> [6, 7, 6]\n",
    "            # step 2: 分别加上point[i][j]\n",
    "            dp = [points[i][j] + dp[j] for j in range(n)]\n",
    "        \n",
    "        return max(dp)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = points[0] # 1st row points [1, 2, 3]\n",
    "        # for 2rd row 1 / 2rd col - > \n",
    "        for i in range(1, m):\n",
    "            # step 1: 对于所有上一行左边的数，都是加上它的坐标减去自己的坐标[从左上方来]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = max(dp[j], dp[j - 1] - 1)\n",
    "            # print(\"*\", dp) [1, 2, 3] -> [2, 7, 6]\n",
    "            # step 2: 对于上一行所有右边的数，都是减去它的坐标加上自己的坐标[从右上方来]\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[j] = max(dp[j], dp[j + 1] - 1)\n",
    "            # print(dp) [1, 2, 3]-> [6, 7, 6]\n",
    "            # 分别加上point[i][j]\n",
    "            dp = [points[i][j] + dp[j] for j in range(n)]\n",
    "        \n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1. 方法一：区间+1， 区间-1， 维护区间最大值，可以用线段树来维护\n",
    "2. 方法二：用两个堆来分别维护左右部分的最大值，将相对变化及时地加到数组中\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            new = [0] * n\n",
    "            l = []\n",
    "            #最大堆\n",
    "            r = [(-dp[j] + j, j) for j in range(n)]\n",
    "            heapq.heapify(r)\n",
    "\n",
    "            for j in range(n):\n",
    "                while r and r[0][1] <= j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                #别人都减一，不好弄，相当于我加1, 这个比较的值只是相对值不是\n",
    "                heapq.heappush(l, (-(dp[j] + j), j))\n",
    "\n",
    "                tar = 0\n",
    "                #取右边（i,n)的最大值\n",
    "                if r:\n",
    "                    x = r[0][1]\n",
    "                    new[j] = dp[x] - (x - j)\n",
    "                #取左边[0,i]的最大值\n",
    "                if l:\n",
    "                    \n",
    "                    x = l[0][1]\n",
    "                    new[j] = max(new[j], dp[x] - (j - x))\n",
    "\n",
    "                new[j] += points[i][j]\n",
    "\n",
    "            dp = new\n",
    "\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = points[0] # 1st row points\n",
    "        # for 2rd row 1 / 2rd col - > \n",
    "        for i in range(1, m):\n",
    "            # step 1: 对于所有上一行左边的数，都是加上它的坐标减去自己的坐标\n",
    "            for j in range(1, n):\n",
    "                dp[j] = max(dp[j], dp[j - 1] - 1)\n",
    "            # step 2: 对于上一行所有右边的数，都是减去它的坐标加上自己的坐标\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[j] = max(dp[j], dp[j + 1] - 1)\n",
    "            # 分别加上point[i][j]\n",
    "            dp = [points[i][j] + dp[j] for j in range(n)]\n",
    "        \n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1. 方法一：区间+1， 区间-1， 维护区间最大值，可以用线段树来维护\n",
    "2. 方法二：用两个堆来分别维护左右部分的最大值，将相对变化及时地加到数组中\n",
    "'''\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m = len(points)\n",
    "        n = len(points[0])\n",
    "        dp = points[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            new = [0] * n\n",
    "            l = []\n",
    "            #最大堆\n",
    "            r = [(-dp[j] + j, j) for j in range(n)]\n",
    "            heapq.heapify(r)\n",
    "\n",
    "            for j in range(n):\n",
    "                while r and r[0][1] <= j:\n",
    "                    heapq.heappop(r)\n",
    "\n",
    "                #别人都减一，不好弄，相当于我加1\n",
    "                heapq.heappush(l, (-(dp[j] + j), j))\n",
    "\n",
    "                tar = 0\n",
    "                #取右边（i,n)的最大值\n",
    "                if r:\n",
    "                    x = r[0][1]\n",
    "                    new[j] = dp[x] - (x - j)\n",
    "                #取左边[0,i]的最大值\n",
    "                if l:\n",
    "                    #print(l)\n",
    "                    #print(dp, j)\n",
    "                    x = l[0][1]\n",
    "                    new[j] = max(new[j], dp[x] - (j - x))\n",
    "\n",
    "                new[j] += points[i][j]\n",
    "\n",
    "            dp = new\n",
    "\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m,n = len(points), len(points[0])\n",
    "\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        for j in range(n):\n",
    "            dp[0][j] = points[0][j]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            lmax = -inf\n",
    "            for j in range(n):\n",
    "                lmax = max(lmax, dp[i-1][j]+j)\n",
    "                # print(lmax)\n",
    "                dp[i][j] = max(dp[i][j],points[i][j]+lmax-j)\n",
    "            rmax = -inf\n",
    "            for j in range(n-1,-1,-1):\n",
    "                rmax = max(rmax ,dp[i-1][j]-j)\n",
    "                dp[i][j] = max(dp[i][j],points[i][j]+rmax+j)\n",
    "        # print(dp)\n",
    "        return max(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        \n",
    "        n,m = len(points),len(points[0])\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        maxPrefix = 0\n",
    "        maxSuffix = [0] * m\n",
    "        for i in range(n) :\n",
    "            for j in range(m) :\n",
    "                if i == 0 :\n",
    "                    f[i][j] = points[i][j]\n",
    "                else :\n",
    "                    f[i][j] = max(maxPrefix - j,maxSuffix[j] + j) + points[i][j]\n",
    "                    maxPrefix = max(maxPrefix,f[i - 1][j] + j)\n",
    "            maxSuffix[-1] = f[i][-1] - (m - 1)\n",
    "            for k in range(m - 2,-1,-1) :\n",
    "                maxSuffix[k] = max(maxSuffix[k + 1],f[i][k] - k)\n",
    "            maxPrefix = 0\n",
    "        return max(f[-1])\n",
    "                    \n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            dp[0][j] = points[0][j]\n",
    "            # ans = max(ans, dp[0][j])\n",
    "\n",
    "        for i in range(1, m):\n",
    "            best = float('-inf')\n",
    "            #k<=j\n",
    "            for j in range(n):\n",
    "                best = max(best, dp[i-1][j]+j)\n",
    "                dp[i][j] = max(dp[i][j], best-j+points[i][j])\n",
    "            #k > j\n",
    "            best = float('-inf')\n",
    "            for j in range(n-1, -1, -1):\n",
    "                best = max(best, dp[i-1][j]-j)\n",
    "                dp[i][j] = max(dp[i][j], best+j+points[i][j])\n",
    "            # ans = max(ans, dp[i][j])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        \n",
    "        n,m = len(points),len(points[0])\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        maxPrefix = 0\n",
    "        maxSuffix = [0] * m\n",
    "        for i in range(n) :\n",
    "            for j in range(m) :\n",
    "                if i == 0 :\n",
    "                    f[i][j] = points[i][j]\n",
    "                else :\n",
    "                    maxPrefix = max(maxPrefix,f[i - 1][j] + j)\n",
    "                    f[i][j] = max(maxPrefix - j,maxSuffix[j] + j) + points[i][j]\n",
    "            maxSuffix[-1] = f[i][-1] - (m - 1)\n",
    "            for k in range(m - 2,-1,-1) :\n",
    "                maxSuffix[k] = max(maxSuffix[k + 1],f[i][k] - k)\n",
    "            maxPrefix = 0\n",
    "        return max(f[-1])\n",
    "                    \n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m,n = len(points),len(points[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        pre_max = [0] * n\n",
    "        suf_max = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[0][i] = points[0][i]\n",
    "            dp[0][n-i-1] = points[0][n-1-i]\n",
    "            if i == 0:\n",
    "                pre_max[i] = dp[0][i]\n",
    "                suf_max[n-1-i] = dp[0][n-i-1] - (n - 1)\n",
    "            else:\n",
    "                pre_max[i] = max(pre_max[i-1], dp[0][i] + i)\n",
    "                suf_max[n-i-1] = max(suf_max[n-i], dp[0][n-i-1] - (n-1-i))\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = max(points[i][j] -j + pre_max[j], points[i][j] + j + suf_max[j])\n",
    "            for k in range(n):\n",
    "                if k == 0:\n",
    "                    pre_max[k] = dp[i][k]\n",
    "                    suf_max[n-1-k] = dp[i][n-k-1] - (n - 1)\n",
    "                else:\n",
    "                    pre_max[k] = max(pre_max[k-1], dp[i][k] + k)\n",
    "                    suf_max[n-k-1] = max(suf_max[n-k], dp[i][n-k-1] - (n-1-k))\n",
    "        return max(dp[-1])\n",
    "s = Solution()\n",
    "s.maxPoints([[1,5],[2,3],[4,2]])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n, m = len(points), len(points[0])\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i == n - 1: return points[i][j]\n",
    "        #     res = t1 = t2 = 0\n",
    "        #     for nxj in range(j + 1):\n",
    "        #         t1 = max(t1, dfs(i + 1, nxj) + nxj)\n",
    "        #     for nxj in range(j + 1, m):\n",
    "        #         t2 = max(t2, dfs(i + 1, nxj) - nxj)\n",
    "        \n",
    "        #     res = max(res, t1, t2)\n",
    "        #     res += points[i][j]\n",
    "        #     return res\n",
    "\n",
    "        # return max(dfs(0, i) for i in range(m))\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        f[0][:] = points[0]\n",
    "        pre_max = [0] * m\n",
    "        suf_max = [0] * m\n",
    "        #print(f)\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                for j in range(m):\n",
    "                    pre_max[j] = max(pre_max[j - 1], f[i][j] + j)\n",
    "                for j in range(m - 1, -1, -1):\n",
    "                    if j == m - 1: suf_max[j] = f[i][j] - j\n",
    "                    else: suf_max[j] = max(suf_max[j + 1], f[i][j] - j)\n",
    "                #print(pre_max, suf_max)\n",
    "            else:\n",
    "                for j in range(m):\n",
    "                    f[i][j] = max(points[i][j] - j + pre_max[j], points[i][j] + j + suf_max[j])\n",
    "                pre_max = [0] * m\n",
    "                suf_max = [0] * m    \n",
    "                for j in range(m):\n",
    "                    pre_max[j] = max(pre_max[j - 1], f[i][j] + j)\n",
    "                for j in range(m - 1, -1, -1):\n",
    "                    if j == m - 1: suf_max[j] = f[i][j] - j\n",
    "                    else: suf_max[j] = max(suf_max[j + 1], f[i][j] - j)\n",
    "                #print(pre_max, suf_max)   \n",
    "        return max(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(points), len(points[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0] = points[0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            mx = -inf\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mx = max(mx, dp[i - 1][j] - j)\n",
    "                dp[i][j] = max(dp[i][j], mx + j + points[i][j])\n",
    "            \n",
    "            mx = -inf\n",
    "            for j in range(n):\n",
    "                mx = max(mx, dp[i - 1][j] + j)\n",
    "                dp[i][j] = max(dp[i][j], mx - j + points[i][j])\n",
    "        # print(dp)\n",
    "        return max(dp[m - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        m = len(points[0])\n",
    "        f = [[0] * m for i in range(n)]\n",
    "        pre_max = [0] * m\n",
    "        suf_max = [0] * m\n",
    "        for j in range(m):\n",
    "            f[0][j] = points[0][j]\n",
    "            x = f[0][j] + j\n",
    "            pre_max[j] = x if j == 0 else max(pre_max[j-1], x)\n",
    "        \n",
    "        for j in range(m-1, -1, -1):\n",
    "            x = f[0][j] - j\n",
    "            suf_max[j] = x if j == m-1 else max(suf_max[j+1], x)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                f[i][j] = max(points[i][j] - j + pre_max[j], points[i][j] + j + suf_max[j])\n",
    "\n",
    "            pre_max = [0] * m\n",
    "            for j in range(m):\n",
    "                x = f[i][j] + j\n",
    "                pre_max[j] = x if j == 0 else max(pre_max[j-1], x)\n",
    "            suf_max = [0] * m\n",
    "            for j in range(m-1, -1, -1):\n",
    "                x = f[i][j] - j\n",
    "                suf_max[j] = x if j == m-1 else max(suf_max[j+1], x)\n",
    "\n",
    "        return max(f[n-1])\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     ans = 0\n",
    "        #     for k in range(m):\n",
    "        #         ans = max(dfs(i-1, k) + points[i][j] - abs(k-j), ans)\n",
    "        #     return ans\n",
    "        \n",
    "        # return max([dfs(n-1, j) for j in range(m)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        m = len(points[0])\n",
    "        f = [[0] * m for i in range(n)]\n",
    "        pre_max = [0] * m\n",
    "        suf_max = [0] * m\n",
    "        for j in range(m):\n",
    "            f[0][j] = points[0][j]\n",
    "            x = f[0][j] + j\n",
    "            pre_max[j] = x if j == 0 else max(pre_max[j-1], x)\n",
    "        \n",
    "        for j in range(m-1, -1, -1):\n",
    "            x = f[0][j] - j\n",
    "            suf_max[j] = x if j == m-1 else max(suf_max[j+1], x)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                f[i][j] = max(points[i][j] - j + pre_max[j], points[i][j] + j + suf_max[j])\n",
    "            pre_max = [0] * m\n",
    "            for j in range(m):\n",
    "                x = f[i][j] + j\n",
    "                pre_max[j] = x if j == 0 else max(pre_max[j-1], x)\n",
    "            \n",
    "            for j in range(m-1, -1, -1):\n",
    "                x = f[i][j] - j\n",
    "                suf_max[j] = x if j == m-1 else max(suf_max[j+1], x)\n",
    "\n",
    "        return max(f[n-1])\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     ans = 0\n",
    "        #     for k in range(m):\n",
    "        #         ans = max(dfs(i-1, k) + points[i][j] - abs(k-j), ans)\n",
    "        #     return ans\n",
    "        \n",
    "        return max([dfs(n-1, j) for j in range(m)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        # dp[i][j] 选中第i行第j列的可以得的最高分数\n",
    "        # dp[i][j] = points[i][j] + max_j1(dp[i+1][j1] - abs(j1-j))\n",
    "        # for j1 <= j\n",
    "        # dp[i][j] = points[i][j] + max_j1(dp[i+1][j1] + j1) - j\n",
    "        # else:\n",
    "        # dp[i][j] = points[i][j] + max_j1(dp[i+1][j1] - j1) + j\n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            dp[m][j] = points[m-1][j-1]\n",
    "        \n",
    "        #for i in range(m-1, 0, -1):\n",
    "        #   for j in range(1, n+1, 1):\n",
    "        #        dp[i][j] = points[i-1][j-1]\n",
    "        #        arr_tmp = 0\n",
    "        #        for j1 in range(1, n+1, 1):\n",
    "        #            arr_tmp = max(arr_tmp, dp[i+1][j1] - abs(j1-j))\n",
    "        #        dp[i][j] = points[i-1][j-1] + arr_tmp\n",
    "        #return max(dp[1])\n",
    "\n",
    "        for i in range(m-1, 0, -1):\n",
    "            maxl = maxr = float(\"-inf\")\n",
    "            for j in range(1, n+1, 1):\n",
    "                maxl = max(maxl, dp[i+1][j]+j)\n",
    "                dp[i][j] = max(dp[i][j], points[i-1][j-1]+maxl-j)\n",
    "            for j in range(n, 0, -1):\n",
    "                maxr = max(maxr, dp[i+1][j]-j)\n",
    "                dp[i][j] = max(dp[i][j], points[i-1][j-1]+maxr+j)\n",
    "        return max(dp[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m,n = len(points), len(points[0])\n",
    "\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        for j in range(n):\n",
    "            dp[0][j] = points[0][j]\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            lmax = -inf\n",
    "            for j in range(n):\n",
    "                lmax = max(lmax, dp[i-1][j]+j)\n",
    "                print(lmax)\n",
    "                dp[i][j] = max(dp[i][j],points[i][j]+lmax-j)\n",
    "            rmax = -inf\n",
    "            for j in range(n-1,-1,-1):\n",
    "                rmax = max(rmax ,dp[i-1][j]-j)\n",
    "                dp[i][j] = max(dp[i][j],points[i][j]+rmax+j)\n",
    "        print(dp)\n",
    "        return max(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == 0:\n",
    "                return points[i][j]\n",
    "            res = 0\n",
    "            for k in range(n):\n",
    "                res = max(res, dfs(i - 1, k) + points[i][j] - abs(j - k))\n",
    "            return res\n",
    "        \n",
    "        m, n = len(points), len(points[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0] = points[0]\n",
    "        pre_max = [0] * n\n",
    "        suf_max = [0] * n\n",
    "        for i in range(1, m):\n",
    "            pre_max[0] = dp[i - 1][0]\n",
    "            for j in range(1, n):\n",
    "                pre_max[j] = max(pre_max[j - 1] - 1, dp[i - 1][j])\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                suf_max[j] = max(suf_max[j + 1] - 1, dp[i - 1][j + 1] - 1)\n",
    "            for j in range(n):\n",
    "                dp[i][j] = max(pre_max[j], suf_max[j]) + points[i][j]\n",
    "        return max(dp[m - 1])\n",
    "        # return max(dfs(m - 1, j) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "寻找重复子问题\n",
    "f[i][j] 表示选中当前格子能够获得的最大分数\n",
    "f[i][j] = max(f[i][j], f[i-1][k] - abs(k - j))\n",
    "f[i][j] = max(f[i-1][0] - j, f[i-1][1] - j + 1, f[i-1][2]-j+2, ..., f[i-1][j], f[i-1][j+1]-1, .., f[i-1][n-1]-(n-1-j))\n",
    "f[i][j+1] = max(f[i-1][0] - j - 1, f[i-1][1] - j, f[i-1][2]-j+1, ..., f[i-1][j] - 1, f[i-1][j+1], .., f[i-1][n-1]-(n-2-j))\n",
    "f[i][j+1] = max(max(f[i-1][0] - j, f[i-1][1] - j + 1, f[i-1][2]-j+2, ..., f[i-1][j]) - 1, max(f[i-1][j+1]-1, .., f[i-1][n-1]-(n-1-j)) + 1)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        m, n = len(points), len(points[0])\n",
    "        f = deepcopy(points)\n",
    "        for i in range(1, m):\n",
    "            left, right = [0] * n, [0] * n\n",
    "            mx = -inf\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                mx = max(mx - 1, f[i-1][j])\n",
    "                right[j] = mx\n",
    "            mx = -inf\n",
    "            for j in range(n):\n",
    "                mx = max(mx - 1, f[i-1][j])\n",
    "                left[j] = mx\n",
    "            k = 0\n",
    "            for j in range(n):\n",
    "                f[i][j] += max(left[j], right[j])\n",
    "                k += 1\n",
    "        return max(f[-1])\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
